|
Proof by exhaustion, also known as proof by cases, perfect induction, or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases and each type of case is checked to see if the proposition in question holds.〔.〕 This is a method of direct proof. A proof by exhaustion contains two stages: # A proof that the cases are exhaustive; i.e., that each instance of the statement to be proved matches the conditions of (at least) one of the cases. # A proof of each of the cases. In the Curry–Howard isomorphism, proof by exhaustion and case analysis are related to ML-style pattern matching. ==Example== To prove that every integer that is a perfect cube is a multiple of 9, or is 1 more than a multiple of 9, or is 1 less than a multiple of 9. Proof: Each cube number is the cube of some integer ''n''. Every integer ''n'' is either a multiple of 3, or 1 more or 1 less than a multiple of 3. So these 3 cases are exhaustive: *Case 1: If ''n'' = 3''p'', then ''n''3 = 27''p''3, which is a multiple of 9. *Case 2: If ''n'' = 3''p'' + 1, then ''n''3 = 27''p''3 + 27''p''2 + 9''p'' + 1, which is 1 more than a multiple of 9. For instance, if ''n'' = 4 then ''n''3 = 64 = 9x7 + 1. *Case 3: If ''n'' = 3''p'' − 1, then ''n''3 = 27''p''3 − 27''p''2 + 9''p'' − 1, which is 1 less than a multiple of 9. For instance, if ''n'' = 5 then ''n''3 = 125 = 9×14 − 1.∎ 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Proof by exhaustion」の詳細全文を読む スポンサード リンク
|